///////////////////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2021, Tom Zhao personal. ("UsingSTLEx")
// This software is a personal tools project by Tom Zhao.
// Description:
///////////////////////////////////////////////////////////////////////////////////////////

// CPP program to find the gray sequence of n bits.
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/* we have 2 choices for each of the n bits either we
can include i.e invert the bit or we can exclude the
bit i.e we can leave the number as it is. */
void grayCodeUtil(vector<int>& res, int n, int& num) {
  // base case when we run out bits to process
  // we simply include it in gray code sequence.
  if (n == 0) {
    res.push_back(num);
    return;
  }

  // ignore the bit.
  grayCodeUtil(res, n - 1, num);

  // invert the bit.
  num = num ^ (1 << (n - 1));
  grayCodeUtil(res, n - 1, num);
}

// returns the vector containing the gray
// code sequence of n bits.
vector<int> grayCodes(int n) {
  vector<int> res;

  // num is passed by reference to keep
  // track of current code.
  int num = 0;
  grayCodeUtil(res, n, num);

  return res;
}

// Driver function.
int main() {
  int n = 3;
  vector<int> code = grayCodes(n);
  for (int i = 0; i < code.size(); i++) cout << code[i] << endl;
  return 0;
}
